package com.exercises;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Exercise120 {
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3, 4));
        triangle.add(Arrays.asList(6, 5, 7));
        triangle.add(Arrays.asList(4, 1, 8, 3));
        System.out.println(new Exercise120().minimumTotal(triangle));

    }


    public int minimumTotal(List<List<Integer>> triangle) {
        int height = triangle.size();
        int width = triangle.get(height - 1).size();
        if (triangle.size() == 0) return 0;
        int[][] dp = new int[2][width];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            int current = i % 2;
            int preview = 1 - current;
            dp[current][0] = dp[preview][0] + triangle.get(i).get(0);
            int j = 1;
            for (; j < triangle.get(i).size() - 1; j++) {
                dp[current][j] = Math.min(dp[preview][j], dp[preview][j - 1]) + triangle.get(i).get(j);
            }
            dp[current][j] = dp[preview][j - 1] + triangle.get(i).get(j);


        }
        int[] lastCloumns = dp[(triangle.size() - 1) % 2];
        int min = lastCloumns[0];
        for (int i = 1; i < lastCloumns.length; i++) {
            min = Math.min(min, lastCloumns[i]);

        }
        return min;
    }
}

